In many memory devices, including random access memory (RAM) devices, data is typically accessed by supplying an address to an array of memory cells and then reading data from the memory cells that reside at the supplied address. However, in content addressable memory (CAM) devices, data is not accessed by initially supplying an address, but rather by initially applying data (e.g., search words) to the device and then performing a search operation to identify one or more entries within the CAM device that contain data equivalent to the applied data and thereby represent a “match” condition. In this manner, data is accessed according to its content rather than its address. Upon completion of the search operation, the identified location(s) containing the equivalent data is typically encoded to provide an address (e.g., CAM array block address+row address within a block) at which the matching entry is located. If multiple matching entries are identified in response to the search operation, then local priority encoding operations may be performed to identify a location of a best or highest priority matching entry. Such priority encoding operations frequently utilize the relative physical locations of multiple matching entries within the CAM device to identify a highest priority matching entry. An exemplary CAM device that utilizes a priority encoder to identify a highest priority matching entry is disclosed in commonly assigned U.S. Pat. No. 6,370,613 to Diede et al., entitled “Content Addressable Memory with Longest Match Detect,” the disclosure of which is hereby incorporated herein by reference. The '613 patent also discloses the use of CAM sub-arrays to facilitate pipelined search operations. Additional CAM devices are described in U.S. Pat. Nos. 5,706,224, 5,852,569 and 5,964,857 to Srinivasan et al. and in U.S. Pat. Nos. 6,101,116, 6,256,216, 6,128,207 and 6,262,907 to Lien et al., the disclosures of which are hereby incorporated herein by reference.
CAM cells are frequently configured as binary CAM cells that store only data bits (as “1” or “0” logic values) or as ternary CAM cells that store data bits and mask bits. As will be understood by those skilled in the art, when a mask bit within a ternary CAM cell is inactive (e.g., set to a logic 1 value), the ternary CAM cell may operate as a conventional binary CAM cell storing an “unmasked” data bit. When the mask bit is active (e.g., set to a logic 0 value), the ternary CAM cell is treated as storing a “don't care” (X) value, which means that all compare operations performed on the actively masked ternary CAM cell will result in a cell match condition. Thus, if a logic 0 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 1 data bit, the compare operation will indicate a cell match condition. A cell match condition will also be indicated if a logic 1 data bit is applied to a ternary CAM cell storing an active mask bit and a logic 0 data bit. Accordingly, if a data word of length N, where N is an integer, is applied to a ternary CAM array block having a plurality of entries therein of logical width N, then a search operation will yield one or more match conditions whenever all the unmasked data bits of an entry in the ternary CAM array block are identical to the corresponding data bits of the applied search word. This means that if the applied search word equals (1011, the following entries will result in a match condition in a CAM comprising ternary CAM cells: {1011}, {X011}, {1X11}, {10X1}, {101X}, {XX11}, {1XX1}, . . . , {1XXX}, {XXXX}.
A plurality of CAM devices may be configured to operate as a search engine that is responsive to instructions generated by a network processing unit (NPU) or other application specific integrated circuit (ASIC). FIG. 1 illustrates a conventional integrated circuit system 10 that utilizes a parallel arrangement of CAM devices 14a-14c and an NPU/ASIC device 12 to perform the functions of a search engine. In this system 10, all CAM devices receive instructions from the NPU 12 at the same time and the results generated by the CAM devices are passed to the last CAM device (CAM 3), which returns a result to the NPU 12. The system 10 includes three primary buses: INSTRUCTION IF (instruction interface bus), CASCADE IF (cascade interface bus) and RESULT IF (result interface bus). The performance of the system of FIG. 1 may be limited by the interface degradation that is typically present when a relatively large number of CAM devices are all loading from the same interface bus (e.g., INSTRUCTION IF).
FIGS. 2A-2B illustrate another integrated circuit system 20 that utilizes a serial cascaded arrangement of master and slave CAM devices 22a-22c to perform the functions of a search engine. Each CAM device is illustrated as having five ports: IN1, IN2, OUT1, OUT2 and OUT3. Input logic is provided between the first input port IN1 and the first output port OUT1. This input logic may be responsible for inspecting and/or altering instructions and/or decomposing instructions into multiple subordinate instructions to be performed by one or more slave CAM devices. The master CAM device 22a is responsible for, inspecting/interpreting and scheduling the instructions the NPU issues to the search engine. These instructions may be issued across a quad data rate (QDR) interface bus, as illustrated. For example, the master CAM device 22a may hold information that is used to translate an indirect address to an absolute address when executing instructions, including read and write instructions. The absolute address is transferred from the master CAM device 22a to the slave CAM devices 22b and 22c in combination with an instruction. Additional cascaded arrangements of CAM devices are illustrated in FIG. 1 of U.S. Pat. No. 6,148,364, FIG. 13 of U.S. Pat. No. 6,240,485 and in U.S. Pat. Nos. 6,137,350, 6,490,650 and 6,493,793. In FIG. 1 of the '364 patent, an instruction bus IBUS is connected to two depth cascaded CAM devices. The '485 patent describes a method and apparatus for implementing a learn instruction in a depth cascaded CAM system.
Notwithstanding these conventional CAM systems that support multi-database search operations, the bandwidth of the NPU interface may be constrained by a typical requirement that each new search key to be used in a search operation be consecutively supplied to the CAM system as a separate word. Accordingly, if a significant percentage of the search words are long words (e.g., N×72 bits, where N≧2), then a relatively large number of data cycles may be required to transfer consecutive search keys across the NPU interface. In these situations, the NPU interface may operate as a bottleneck to system performance.